{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "已知：\n",
    "\n",
    "    AList = [1,2,3]\n",
    "    BSet = {1,2,3}\n",
    "    \n",
    "(1) 从 AList 和 BSet 中 查找 4，最坏时间复杂度那个大？\n",
    "(2) 从 AList 和 BSet 中 插入 4，最坏时间复杂度那个大？\n",
    "\n",
    "124.python 单例模式的实现方法\n",
    "126.找出列表中的重复数字\n",
    "127.找出列表中的单个数字\n",
    "128.写一个冒泡排序\n",
    "129.写一个快速排序\n",
    "130.写一个拓扑排序\n",
    "131.python 实现一个二进制计算\n",
    "132.有一组“+”和“-”符号，要求将“+”排到左边，“-”排到右边，写出具体的实现方法。\n",
    "133.单链表反转\n",
    "134.交叉链表求交点\n",
    "135.用队列实现栈\n",
    "136.找出数据流的中位数\n",
    "137.二叉搜索树中第 K 小的元素\n",
    "42.如何交换字典 {\"A\"：1,\"B\"：2}的键和值？\n",
    "43.Python 里面如何实现 tuple 和 list 的转换？\n",
    "44.我们知道对于列表可以使用切片操作进行部分元素的选择，那么如何对生成器类型的对象实现相同的功能呢？\n",
    "45.请将[i for i in range(3)]改成生成器\n",
    "46.a=\"hello\"和 b=\"你好\"编码成 bytes 类型\n",
    "47.下面的代码输出结果是什么？\n",
    " ———————————————— \n",
    "49.Python 交换两个变量的值\n",
    "50.在读文件操作的时候会使用 read、readline 或者 readlines，简述它们各自的作用\n",
    "51.json 序列化时，可以处理的数据类型有哪些？如何定制支持 datetime 类型？\n",
    "52.json 序列化时，默认遇到中文会转换成 unicode，如果想要保留中文怎么办？\n",
    "53.有两个磁盘文件 A 和 B，各存放一行字母，要求把这两个文件中的信息合并(按字母顺序排列)，输出到一个新文件 C 中。\n",
    "54.如果当前的日期为 20190530，要求写一个函数输出 N 天后的日期，(比如 N 为 2，则输出 20190601)。\n",
    "55.写一个函数，接收整数参数 n，返回一个函数，函数的功能是把函数的参数和 n 相乘并把结果返回。\n",
    "56.下面代码会存在什么问题，如何改进？\n",
    "def strappend(num):\n",
    "    str='first'\n",
    "    for i in range(num):\n",
    "        str+=str(i)\n",
    "    return str\n",
    "\n",
    "57.一行代码输出 1-100 之间的所有偶数。\n",
    "58.with 语句的作用，写一段代码？\n",
    "59.python 字典和 json 字符串相互转化方法\n",
    "60.请写一个 Python 逻辑，计算一个文件中的大写字母数量\n",
    "61. 请写一段 Python连接 Mongo 数据库，然后的查询代码。\n",
    "62.说一说 Redis 的基本类型。\n",
    "63. 请写一段 Python连接 Redis 数据库的代码。\n",
    "64. 请写一段 Python 连接 MySQL 数据库的代码。\n",
    "65.了解 Redis 的事务么？\n",
    "66.了解数据库的三范式么？\n",
    "67.了解分布式锁么？\n",
    "68.用 Python 实现一个 Reids 的分布式锁的功能。\n",
    "69.写一段 Python 使用 Mongo 数据库创建索引的代码。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(nums1, m, nums2, n):\n",
    "    \"\"\"\n",
    "    Do not return anything, modify nums1 in-place instead.\n",
    "    使用 归并排序的 merge 过程，nums1 声明为 global ,或者使用 copy  无效；结果判断使用的引用地址\n",
    "    \"\"\"\n",
    "    i,j = 0, 0\n",
    "    temp = []\n",
    "    if m>1 and n<1:\n",
    "        return nums1\n",
    "    elif m<1 and n > 1:\n",
    "        nums1 = nums2\n",
    "    else:\n",
    "        import pdb\n",
    "        pdb.set_trace()\n",
    "        while i < m and j < n:\n",
    "            if nums1[i] <= nums2[j]:\n",
    "                print(nums1[i])\n",
    "                if nums1[i] == 0:\n",
    "                    nums1[i] = nums2[j]\n",
    "                    j += 1\n",
    "                    print(nums1, i, nums2,j)\n",
    "                i += 1\n",
    "            else:\n",
    "                temp = nums1[i:m]\n",
    "                nums1[:i].append(nums2[j])\n",
    "                j += 1\n",
    "                i += 1\n",
    "                m += 1\n",
    "                nums1[i+1:m] = temp\n",
    "        if j < n:\n",
    "            nums1.extend(nums2[j:n])\n",
    "# 输入:\n",
    "nums1 = [1,2,3,0,0,0]\n",
    "m = 3\n",
    "nums2 = [2,5,6]\n",
    "n = 3\n",
    "merge(nums1, m, nums2, n)\n",
    "print(nums1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "计算将A转换为B所需的位数\n",
    "    在重复元素array中查找两个非重复元素\n",
    "    找到具有相同设置位数的下一个较大和下一个较小的数字\n",
    "    给定 n 个项目的重量和值，将这些物品放入容量为 W 的背包中背包中的最大总价值。\n",
    "    给定一根长度为 n 英寸的杆和一系列价格，其中包含所有尺寸小于 n 的尺寸的价格。确定通过切割杆和销售件可获得的最大值。\n",
    "    给定两个字符串 str1 和 str2 以及可以在 str1 上执行的操作。查找所需的最小编辑数（操作）将’str1’转换为’str2’\n",
    "    给定 0 和 1 的二维矩阵，找到最大的广场，其中包含全部 1。\n",
    "    找到两者中存在的最长子序列的长度。子序列是以相同的相对顺序出现的序列，但不一定是连续的。\n",
    "    找到给定序列的最长子序列的长度，以便对子序列的所有元素进行排序，按顺序递增。\n",
    "    给定成本矩阵成本[] []和成本[] []中的位置（m，n），\n",
    "    将一个集合划分为两个子集，使得子集和的差异最小\n",
    "    给定一组非负整数和一个值和，确定是否存在给定集合的子集，其总和等于给定总和。\n",
    "    HackerRank 问题算法 DP\n",
    "    给定距离 dist，计算用 1,2 和 3 步覆盖距离的总方式\n",
    "    在字符板中查找所有可能的单词\n",
    "    广度优先搜索遍历\n",
    "    深度优先搜索遍历\n",
    "    在有向图中检测周期\n",
    "    检测无向图中的循环\n",
    "    Dijkstra的最短路径算法\n",
    "    在给定的边缘加权有向图中找出每对顶点之间的最短距离\n",
    "    图形实现\n",
    "    Kruskal的最小生成树算法\n",
    "    拓扑排序\n",
    "    两个字符串是否是变位词\n",
    "    单链表逆置\n",
    "    前序中序求后序\n",
    "    求两棵树是否相同\n",
    "    求最大树深\n",
    "    前中后序遍历\n",
    "    二叉树节点\n",
    "    层次遍历\n",
    "    深度遍历\n",
    "    找零问题\n",
    "    \n",
    "Python 最常见的 170 道面试题解析：2019 最新\n",
    "https://blog.csdn.net/valada/article/details/90761019"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "/*\n",
    "**题目：\n",
    "\n",
    "找出数组中所有满足这样条件的数字：\n",
    "\n",
    "1、数字左边的数都不大于它（对第一个数字没有这个要求）\n",
    "\n",
    "2、数字右边的数都不小于它（对最后一个数字没有这个要求）\n",
    "**思路：\n",
    "\n",
    "使用一个数组rightMin[ ]记录原始数组array[i]右边（包括自己）的最小值。\n",
    "\n",
    "假设原始数组为array[ ] = {7,10,2,6,19,22,32}\n",
    "\n",
    "                   则rightMin[ ] = {2,2,2,6,19,22,32}\n",
    "\n",
    "然后遍历数组，维持一个前面数组的最大值，只要当前值满足 >= leftMax 并且 == rightMin[i] 则当前数字满足条件。*/\n",
    "#include<iostream>\n",
    "//#include<string>\n",
    "//#include<vector>\n",
    "using namespace std;\n",
    " \n",
    "void smallLarge(int *nums , int len)\n",
    "{\n",
    "\tif(nums == NULL || len <= 0)\n",
    "\t\treturn;\n",
    "\tint *rightMin = new int[len]();\n",
    "\trightMin[len-1] = nums[len-1];\n",
    "\tfor(int i = len - 2 ; i >= 0 ; i--)\n",
    "\t{\n",
    "\t\trightMin[i] = min(nums[i] , rightMin[i+1]);\n",
    "\t}\n",
    "\tint leftMax = 0x80000000;//最小值\n",
    "\tfor(int i = 0 ; i < len ; i++)\n",
    "\t{\n",
    "\t\tif(nums[i] >= leftMax)\n",
    "\t\t{\n",
    "\t\t\tleftMax = nums[i];\n",
    "\t\t\tif(nums[i] == rightMin[i])\n",
    "\t\t\t\tcout<<nums[i]<<endl;\n",
    "\t\t}\n",
    "\t}\n",
    "\tdelete [] rightMin;\n",
    "}\n",
    " \n",
    "int main()\n",
    "{\n",
    "\tint nums[7] = {7,10,2,6,19,22,32};\n",
    "\tsmallLarge(nums , 7);\n",
    "\treturn 0;\n",
    "} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 数字i 都大于左边的数字，都小于右边的数字\n",
    "\n",
    "listA = [1,2,4,3]\n",
    "rst = [1,2]\n",
    "def findI(listA):\n",
    "    rst = []\n",
    "    length = len(listA)\n",
    "    for i in range(length):\n",
    "        if i == 0 and listA[0] < min(listA[1:]):\n",
    "            rst.append(listA[0])\n",
    "        elif i == length - 1 and listA[-1] > max(listA[:-1]):\n",
    "            rst.append(listA[-1])\n",
    "            break\n",
    "        elif listA[i] <= min(listA[i:]) and listA[i] > max(listA[:i]):\n",
    "            rst.append(listA[i])\n",
    "        else:\n",
    "            continue\n",
    "    return rst\n",
    "print(listA)\n",
    "print(findI(listA)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定字符串，删除开始和结尾处的空格，并将中间的多个连续的空格合并成一个。\n",
    "# 比如 “   I like     football    ” 会变成 \"I like football\"\n",
    "\n",
    "class StripStr():\n",
    "    def __init__(self):\n",
    "        pass\n",
    "    \n",
    "    def get_real_str(self, strs=None):\n",
    "        strs =\"   I like     football    \"  # 会变成 \"I like football\"\n",
    "        strs_list = strs.split(\" \")\n",
    "        strs_list = [iStr for iStr in strs_list if len(iStr.strip())]\n",
    "        new_strs = \" \".join(strs_list).strip()\n",
    "        print(new_strs)\n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    ns = StripStr()\n",
    "    ns.get_real_str()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 从类似如下的文本文件中读取出所有的姓名，并打印出重复的姓名和重复的次数，并按重复次数排序：\n",
    "# 1,张三,28\n",
    "# 2,李四,35\n",
    "# 3,张三,28\n",
    "# 4,王五,35\n",
    "# 5,张三,28\n",
    "# 6,李四,35\n",
    "# 7,赵六,28\n",
    "# 8,田七,35\n",
    "\n",
    "class GetRepeatStr():\n",
    "    def __init__(self):\n",
    "        self.strs = \"\"\"1,张三,28\n",
    "                        2,李四,35\n",
    "                        3,张三,28\n",
    "                        4,王五,35\n",
    "                        5,张三,28\n",
    "                        6,李四,35\n",
    "                        7,赵六,28\n",
    "                        8,田七,35\"\"\"\n",
    "\n",
    "    \n",
    "    def count_repeat_num(self, strs=None):\n",
    "        strs_lines = self.strs.split('\\n')\n",
    "        strs_lines = [iStr.split(\",\")[1] for iStr in strs_lines]\n",
    "        strs_count = []\n",
    "        real_strs = set(strs_lines)\n",
    "        for iStr in real_strs:\n",
    "            count = 0\n",
    "            for temp_str in strs_lines:\n",
    "                if iStr in temp_str:\n",
    "                    count += 1\n",
    "            strs_count.append({\"name\":iStr,\"count\":count})\n",
    "#         print(strs_count)\n",
    "        return strs_count\n",
    "    \n",
    "    def sort_strs_count(self, strs_count=None):\n",
    "        strs_count = sorted(strs_count, key=lambda strs:strs[\"count\"] )\n",
    "#         print(strs_count)\n",
    "        return strs_count\n",
    "        \n",
    "    def print_sorted_repeat_strs(self, strs=None):\n",
    "        strs_count = self.count_repeat_num()\n",
    "        sorted_strs = self.sort_strs_count(strs_count)\n",
    "        print(sorted_strs)\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    strs = GetRepeatStr()\n",
    "    strs.print_sorted_repeat_strs()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# \n",
    "\n",
    "def add():\n",
    "    # print(\"Please input the add numbers, split by backspace' ':  \",end='')\n",
    "    inStr = input()\n",
    "    a, b = inStr.split(' ')\n",
    "    rst = int(a) + int(b)\n",
    "    # print(\"The sum is: {}\".format(rst))\n",
    "    print(rst)\n",
    "\n",
    "def right_number(num):\n",
    "    num = int(num)\n",
    "    if num <= 2000 and num >= -2000:\n",
    "        return num\n",
    "    else:\n",
    "        return None\n",
    "\n",
    "def over_space():\n",
    "    #  集合覆盖\n",
    "    s1 = input()\n",
    "    s1 = [num for num in s1.split(' ') if right_number(num)]\n",
    "    if None in s1:\n",
    "        return None\n",
    "    s1_x1, s1_y1, s1_x2, s1_y2 = s1\n",
    "    s2 = input()\n",
    "    s2 = [right_number(num) for num in s2.split(' ') ]\n",
    "    if None in s2:\n",
    "        return None\n",
    "    s2_x1, s2_y1, s2_x2, s2_y2 = s2\n",
    "    col = min(int(s1_x2),int(s2_x2)) - max(int(s1_x1),int(s2_x1))\n",
    "    row = min(int(s1_y2),int(s2_y2)) - max(int(s1_y1),int(s2_y1))\n",
    "    overSpace = col * row\n",
    "    print(overSpace)\n",
    "\n",
    "import copy\n",
    "from collections import defaultdict\n",
    "def helloworld(taskStr=\"helloworld\"):\n",
    "    s = input()\n",
    "    s = list(s) \n",
    "    if len(taskStr) > len(s):\n",
    "        return False\n",
    "    s1 = ''.join([char for char in s if char in taskStr])\n",
    "    tempIndex = 0\n",
    "    for char in taskStr:\n",
    "        if char in s1:\n",
    "            sIndex = s1.index(char)\n",
    "            if tempIndex <= sIndex:\n",
    "                tempIndex = sIndex\n",
    "            else:\n",
    "                print(\"false\")\n",
    "                return False\n",
    "    print(\"true\")\n",
    "    return True\n",
    "\n",
    "    # sd = defaultdict(list)\n",
    "    # td = defaultdict(list)\n",
    "    # for k,va in [(v,i) for i,v in enumerate(s1)]:\n",
    "    #     sd[k].append(va)\n",
    "    # for k,va in [(v,i) for i,v in enumerate(taskStr)]:\n",
    "    #     td[k].append(va)\n",
    "    # sKey = sd.keys()\n",
    "    # tKey = td.keys()\n",
    "    # if len(sKey) < len(tKey):\n",
    "    #     return False\n",
    "    # for key in tKey:\n",
    "    #     if key not in sKey:\n",
    "    #         return False\n",
    "    #     if tKey[key] == sKey[key]:\n",
    "\n",
    "    # commonItems = {k: sd[k] for k in sd if k in td and td[k] == sd[k]}\n",
    "\n",
    "    # commmonStr = ''.join(commonItems.values())\n",
    "    # commonIndex = commonItems.keys()\n",
    "    # if commmonStr != taskStr:\n",
    "    #     print(\"false\")\n",
    "    #     return False\n",
    "    # if commonIndex != sorted(commonIndex,reversed=False):\n",
    "    #     print(\"false\")\n",
    "    #     return False\n",
    "    # print(\"true\")\n",
    "    # return True\n",
    "\n",
    "def huiwen(s,i,step,rst):\n",
    "    #     判断回文字符串\n",
    "    if i > len(s) - 1:\n",
    "        return rst\n",
    "    if s[i] != s[i+step] and s[i+step] == \"\" and i+step < len(s) - 1:\n",
    "        step += 1\n",
    "        return huiwen(s,i,step,rst)\n",
    "    elif s[i] == s[i+step] and i+step < len(s) - 1:\n",
    "        rst = s[i] + '+'*step + s[i+step]\n",
    "        i += step\n",
    "        step = 1\n",
    "        return huiwen(s,i,step,rst)\n",
    "    elif s[i] != s[i+step] and s[i+step] != \"\" and i+step < len(s) - 1:\n",
    "        i += step\n",
    "        step = 1\n",
    "        return huiwen(s,i,step,rst)\n",
    "    else:\n",
    "        rst = s[i] + '_'*step + s[i+step]\n",
    "        return rst\n",
    "\n",
    "def asser_huiwen(s):\n",
    "    s = s.strip('_')\n",
    "    length = len(s)\n",
    "    s = s.split(\"_\")\n",
    "    # s.remove(\"\")\n",
    "    rst = \"\"\n",
    "    huiwen(s,i=0,step=1,rst=rst)\n",
    "    print(rst)\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    # helloworld()\n",
    "    print(asser_huiwen(\"__aa_ab__ab\"))\n",
    "\"\"\" \n",
    "** E - 不连续子串判断\n",
    "\n",
    "    实现⼀个函数，判断helloworld是否是给定字符串的不连续子串\n",
    "\n",
    "即helloworld的每个字母均在给定字符串中出现，并且需要保持先后顺序但可以允许不相邻\n",
    "\n",
    "如helllllllo wwwwwwworld 符合条件，如红色的标记所示。\n",
    "\n",
    "但helolllllworld不符合条件。\n",
    "\n",
    "\n",
    "## D - _与+字符变换 \n",
    "    给定一个只包含小写字母和‘_’的字符串，输出如下变换后的结果：\n",
    "\n",
    "    字符串被连续的'_'分成了若干子串，如果一段连续的'_'两侧是相同的子串，则将这段'_'的每个字符变为'+'\n",
    "\n",
    "\n",
    "## F - 观察3D空间中的线段是否相交 \n",
    "    3D空间里，给定两条长度非零的线段S1、S2（S1与S2不共面），以及一个点O（不在S1、S2上）。\n",
    "\n",
    "    判断以O点作为观测点观察，S1和S2是否相交（即S1和S2至少要有一个公共点）。 \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 初始化链表\n",
    "class Node:\n",
    "    def __init__(self,value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "\n",
    "class LinkList(object):\n",
    "    def __init__(self):\n",
    "        self.head = Node(\"head\")\n",
    "        \n",
    "    def append_list(self,head,value):\n",
    "        newNode = Node(value)\n",
    "        head.next = newNode\n",
    "        \n",
    "    def display_list(self, head=None):\n",
    "        tempHead = head or self.head\n",
    "        count = -1\n",
    "        while tempHead.next != None:\n",
    "            count += 1\n",
    "            print(tempHead.value,end=\" \")\n",
    "            tempHead = tempHead.next\n",
    "        print(\"\\nThe count of single Link list is : {}\".format(count))\n",
    "\n",
    "    def delete_item(self,value):\n",
    "        tempHead = self.head\n",
    "        deleteNode = tempHead.next\n",
    "        if tempHead.value == value:\n",
    "            tempHead = tempHead.next\n",
    "            return \n",
    "        elif deleteNode.value == value:\n",
    "            tempHead.next = deleteNode.next\n",
    "            return \n",
    "        else:\n",
    "            while deleteNode.value != value:\n",
    "                tempHead = tempHead.next\n",
    "                deleteNode = tempHead.next\n",
    "            tempHead.next = deleteNode.next\n",
    "        \n",
    "\n",
    "    def init_list_by_arry(self,arry=[]):\n",
    "        head = self.head\n",
    "        if arry:\n",
    "            for item in arry:\n",
    "                self.append_list(head,item)\n",
    "                head = head.next\n",
    "        else:\n",
    "            raise IOError(\"Arry is null ! \")\n",
    "    \n",
    "    def reverse_list_by_swap(self):\n",
    "        if self.head is None or self.head.next is None:\n",
    "            return self.head\n",
    "        head = self.head\n",
    "        pre = None\n",
    "        cur = head\n",
    "        while cur:\n",
    "            head = cur\n",
    "            tmp = cur.next\n",
    "            cur.next = pre\n",
    "            pre = cur\n",
    "            cur = tmp\n",
    "        return head\n",
    "    \n",
    "    def reverse_list_recursion(self,head=None, newhead=None):\n",
    "        head = head or self.head\n",
    "        if head is None:\n",
    "            return  \n",
    "        if head.next is None:\n",
    "            rhead = head \n",
    "        else:\n",
    "            rhead = self.reverse_list_recursion(head=head.next,newhead=rhead)\n",
    "            head.next.next = head\n",
    "            head.next = None\n",
    "        return rhead\n",
    "        \n",
    "def task():\n",
    "    begin = yield\n",
    "    end = yield  \n",
    "    yield\n",
    "    for x in range(begin,end):\n",
    "        yield x\n",
    "\n",
    "\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    ll = LinkList()\n",
    "    ll.init_list_by_arry([1,2,3,4,5,6,7,8,9])\n",
    "    ll.display_list()\n",
    "    # ll.delete_item(5)\n",
    "    rl = ll.reverse_list_by_swap()\n",
    "    ll.display_list(rl)\n",
    "    # rl = ll.reverse_list_recursion()\n",
    "    # ll.display_list(rl)\n",
    "    t = task()\n",
    "    t.send(None)\n",
    "    t.send(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 初反转化链表\n",
    "class Node:\n",
    "    def __init__(self,value):\n",
    "        self.val = value\n",
    "        self.next = None\n",
    "\n",
    "class LinkList(object):\n",
    "    def __init__(self):\n",
    "        self.head = Node(\"head\")\n",
    "        \n",
    "    def append_list(self,value):\n",
    "        point = self.head\n",
    "        newNode = Node(value)\n",
    "        point.next = newNode\n",
    "        point = point.next\n",
    "        \n",
    "    def display_list(self):\n",
    "        tempHead = self.head\n",
    "        while tempHead.next != None:\n",
    "            print(tempHead.value)\n",
    "            tempHead = tempHead.next\n",
    "            \n",
    "    def init_list_by_arry(self,arry=[]):\n",
    "        if arry:\n",
    "            for item in arry:\n",
    "                self.append_list(item)\n",
    "        else:\n",
    "            raise IOError(\"Arry is null ! \")\n",
    "    \n",
    "class RecurseList:\n",
    "    def non_recurse(head):\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        pre = None\n",
    "        cur = head\n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    ll = LinkList()\n",
    "    ll.init_list_by_arry([1,2,3,4,5,6,7,8,9])\n",
    "    ll.display_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"二叉树遍历\n",
    "# 参考连接：https://zhuanlan.zhihu.com/p/33977566\n",
    "\"\"\"\n",
    "\n",
    "class BitNode:\n",
    "    def __init__(self,data):\n",
    "        self.data = data\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "    def has_value(self, value):\n",
    "        if self.data == value:\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "class BitTree:\n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        self.bitList = []\n",
    "\n",
    "    def add_bit_item(self, item):\n",
    "        if not isinstance(item, BitNode):\n",
    "            item = BitBode(item)\n",
    "        if self.root is None:\n",
    "            self.root = item\n",
    "            self.bitList.append(item)\n",
    "        else:\n",
    "            rootNode = self.bitList[0]\n",
    "            while True:\n",
    "                if item.data < rootNode.data:\n",
    "                    # 往左移\n",
    "                    if rootNode.left == None:\n",
    "                        rootNode.left = item\n",
    "                        self.bitList.append(item)\n",
    "                        break\n",
    "                    else:\n",
    "                        rootNode = rootNode.left\n",
    "                elif item.data > rootNode.data:\n",
    "                    # 往右移\n",
    "                    if rootNode.right == None:\n",
    "                        rootNode.right = item\n",
    "                        self.bitList.append(item)\n",
    "                        break\n",
    "                    else:\n",
    "                        rootNode = rootNode.right\n",
    "\n",
    "    def front_traverse(self,root):\n",
    "        if root == None:\n",
    "            return None\n",
    "        print(root.data)\n",
    "        self.front_traverse(root.left)\n",
    "        self.front_traverse(root.right)\n",
    "\n",
    "def display_bitTree(bitTree):\n",
    "    if not isinstance(bitTree, BitTree):\n",
    "        raise ValueError(\"类型错误\")\n",
    "    for bit in bitTree.bitList:\n",
    "        print(bit.data)\n",
    "\n",
    "def middle_traverse(root):\n",
    "    if root == None:\n",
    "        return None\n",
    "    middle_traverse(root.left)\n",
    "    print(root.data)\n",
    "    middle_traverse(root.right)\n",
    "\n",
    "def last_traverse(root):\n",
    "    if root == None:\n",
    "        return None\n",
    "    last_traverse(root.left)\n",
    "    last_traverse(root.right)\n",
    "    print(root.data)\n",
    "\n",
    "def floor_traverse(root):\n",
    "    # 按层次遍历\n",
    "    from collections import deque\n",
    "    q = deque()\n",
    "    if root == None:\n",
    "        return None\n",
    "    q.append(root)\n",
    "    while q:\n",
    "        node = q.pop()\n",
    "        print(node.data)\n",
    "        if node.left != None:\n",
    "            q.append(node.left)\n",
    "        if node.right != None:\n",
    "            q.append(node.right)\n",
    "    \n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    node1 = BitNode(15)\n",
    "    node2 = BitNode(9)\n",
    "    node3 = BitNode(16)\n",
    "    node4 = BitNode(8)\n",
    "    node5 = BitNode(10)\n",
    "    node6 = BitNode(17)\n",
    "    node7 = BitNode(20)\n",
    "    bitTree = BitTree()\n",
    "    for i in [node1,node2,node3,node4,node5,node6,node7,]:\n",
    "        bitTree.add_bit_item(i)\n",
    "    \n",
    "    display_bitTree(bitTree)\n",
    "    # 15 9 16 8 10 17 20\n",
    "    print(\"先序遍历：\")\n",
    "    bitTree.front_traverse(bitTree.root)\n",
    "    print(\"中序遍历：\")\n",
    "    middle_traverse(bitTree.root)\n",
    "    print(\"后序遍历：\")\n",
    "    last_traverse(bitTree.root)\n",
    "    print(\"按层次遍历：\")\n",
    "    floor_traverse(bitTree.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 类方法重载\n",
    "#! /usr/bin/env python\n",
    "# -*- coding: UTF-8 -*-\n",
    "from __future__ import division\n",
    "       \n",
    "class Vector:\n",
    "    \n",
    "    def __init__(self,x,y,z):\n",
    "        self.vt = (x,y,z)\n",
    "    \n",
    "    def __add__(self,other):\n",
    "        self.vt = map(sum,zip(self.vt,other.vt))\n",
    "        return self.__str__()\n",
    "        \n",
    "    def sub(self,si):\n",
    "        return si[0] - si[1]\n",
    "    \n",
    "    def __sub__(self,other):     \n",
    "        self.vt = map(self.sub,zip(self.vt,other.vt))\n",
    "        return self.__str__()\n",
    "        \n",
    "    def mul(self,si):\n",
    "        return si[0] * si[1]\n",
    "    \n",
    "    def div(self,si):\n",
    "        return si[0] / si[1]\n",
    "    \n",
    "    def __mul__(self,other):\n",
    "        self.vt = map(self.mul,zip(self.vt,[other]*len(list(self.vt))))\n",
    "        return self.__str__()\n",
    "    \n",
    "    def __truediv__(self,other):\n",
    "        self.vt = map(self.div,zip(self.vt,[other]*len(list(self.vt))))\n",
    "        return self.__str__()\n",
    "    \n",
    "    def __str__(self):\n",
    "        self.vt = list(self.vt)\n",
    "        for i in range(len(self.vt)):\n",
    "            self.vt[i] = float(\"{:.1f}\".format(self.vt[i]))     \n",
    "        return str(tuple(self.vt))\n",
    "        \n",
    "\n",
    "        \n",
    "if __name__ == '__main__':\n",
    "    alist = input().split()\n",
    "    blist = input().split()\n",
    "    n = float(input())\n",
    "    a = Vector(float((alist[0])),float(alist[1]),float(alist[2]))\n",
    "    b = Vector(float(blist[0]),float(blist[1]),float(blist[2]))    \n",
    "    \n",
    "    print (\"{} {} {} {}\".format(a+b,a-b,a*n,a/n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 类继承\n",
    "#! /usr/bin/env python\n",
    "# -*- coding: UTF-8 -*-\n",
    "from __future__ import division\n",
    "\n",
    "class People:\n",
    "\n",
    "    def __init__(self,name,age):\n",
    "        self.name = name\n",
    "        self.age = age\n",
    "        \n",
    "    def getName(self):\n",
    "        return self.name\n",
    "    \n",
    "    def getAge(self):\n",
    "        return self.age\n",
    "\n",
    "class Student(People):\n",
    "    \n",
    "    def __init__(self,name,age,id):\n",
    "        People.__init__(self, name, age)\n",
    "        self.id = id\n",
    "        \n",
    "    def getId(self):\n",
    "        return self.id\n",
    "\n",
    "class Xdict(dict):\n",
    "    \n",
    "    def __init__(self,new_dict):\n",
    "        dict.__init__(self)\n",
    "        self.new_dict = dict(new_dict)\n",
    "        \n",
    "    def getKeys(self,value):\n",
    "        if value in self.new_dict.values():\n",
    "            key_list = []\n",
    "            for ikey in self.new_dict.keys():\n",
    "                if value in self.new_dict[ikey]:\n",
    "                    key_list.append(ikey)\n",
    "            return key_list\n",
    "        else:\n",
    "            return None\n",
    "\n",
    "        \n",
    "class Vector:\n",
    "    \n",
    "    def __init__(self,x,y,z):\n",
    "        self.vt = (x,y,z)\n",
    "    \n",
    "    def __add__(self,other):\n",
    "        return self.format(map(sum,zip(self.vt,other.vt)))\n",
    "        \n",
    "    def sub(self,si):\n",
    "        return si[0] - si[1]\n",
    "    \n",
    "    def __sub__(self,other):     \n",
    "        return self.format(map(self.sub,zip(self.vt,other.vt)))\n",
    "        \n",
    "    def mul(self,si):\n",
    "        return si[0] * si[1]\n",
    "    \n",
    "    def div(self,si):\n",
    "        return si[0] / si[1]\n",
    "    \n",
    "    def __mul__(self,other):\n",
    "        return self.format(map(self.mul,zip(self.vt,[other]*len(self.vt))))\n",
    "\n",
    "    \n",
    "    def __truediv__(self,other):\n",
    "        return self.format(map(self.div,zip(self.vt,[other]*len(self.vt))))\n",
    "    \n",
    "    def format(self,mps):\n",
    "        for i in range(len(mps)):\n",
    "            mps[i] = float(\"{:.1f}\".format(mps[i]))\n",
    "        return str(tuple(mps))\n",
    "    \n",
    "    def __str__(self): \n",
    "        for i in range(len(self.vt)):\n",
    "            self.vt[i] = float(\"{:.1f}\".format(self.vt[i]))     \n",
    "        return str(tuple(self.vt))\n",
    "        \n",
    "\n",
    "        \n",
    "if __name__ == '__main__':\n",
    "    alist = input().split()\n",
    "    blist = input().split()\n",
    "    n = float(input())\n",
    "    \n",
    "    a = Vector(float(alist[0]),float(alist[1]),float(alist[2]))    \n",
    "    b = Vector(float(blist[0]),float(blist[1]),float(blist[2]))    \n",
    "    \n",
    "    print \"{} {} {} {}\".format(a+b,a-b,a*n,a/n)\n",
    "\n",
    " #==============================================================================\n",
    " #    name = input()\n",
    " #    age = int(input())\n",
    " #    id = input()\n",
    " #    \n",
    " #    S = Student(name,age,id)\n",
    " #    print(\"{} {} {}\".format(S.getName(), S.getAge(),S.getId()))\n",
    " # \n",
    " #    p = People(name,age)\n",
    " #    print(\"{} {}\".format(p.getName(),p.getAge()))\n",
    " #    alist = list(input().split())\n",
    " #    blist = list(input().split())\n",
    " #    target = input()\n",
    " #    d = Xdict(zip(alist,blist))\n",
    " #    print(sorted(d.getKeys(target)))\n",
    " #=============================================================================="
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" 实现列表中重复元素最后一次出现的索引位置\n",
    "\n",
    ">>> get_last_exist_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 5)\n",
    "5\n",
    ">>> get_last_exist_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 8)\n",
    "12\n",
    ">>> get_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 5)\n",
    "5\n",
    ">>> get_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 8)\n",
    "12\n",
    " \"\"\"\n",
    "\n",
    "listA = [3,4,5,6,6,5,4,3,2,1,7,8,8,3]\n",
    "target = 5\n",
    "def get_last_exist_dir(listA, target):\n",
    "    # 倒置 list，查找其第一次出现的位置\n",
    "    return len(listA)- 1 - listA[::-1].index(target) \n",
    "    # for index, num in listA[::-1]:\n",
    "    #     if num == target:\n",
    "    #         return index\n",
    "\n",
    "def get_dir(listA, target):\n",
    "    # 二分法 和 快速排序想法尝试，并不能有效解决所有情况！\n",
    "    rst = None\n",
    "    length = len(listA)\n",
    "    left = 0\n",
    "    right = length - 1\n",
    "    # listA = listA[::-1]\n",
    "    while left < right:\n",
    "        mid = left + (right-left) // 2\n",
    "        # if target in listA[mid:]:\n",
    "        if target >= listA[mid]:\n",
    "            rst = mid\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    return rst\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    import doctest\n",
    "    doctest.testmod()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#!/usr/bin/env python\n",
    "# -*- coding:utf-8 -*-\n",
    "\n",
    "def divisors(num):\n",
    "    if num < 6:\n",
    "        return 0\n",
    "    divs = []\n",
    "    for x in range(num//2,0,-1):\n",
    "        if num % x == 0:\n",
    "           divs.append(x) \n",
    "        else:\n",
    "            continue\n",
    "    if len(divs):\n",
    "        return divs, num\n",
    "    \n",
    "def checkDivisors(divs,num):\n",
    "    sum = 0\n",
    "    for di in divs:\n",
    "        sum += di\n",
    "    if sum == num:\n",
    "        return Num\n",
    "\n",
    "def countWanmeishu(nums):\n",
    "    \"\"\"\n",
    "    完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。\n",
    "    它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。\n",
    "    如果一个数恰好等于它的因子之和，则称该数为“完全数”。\n",
    "    第一个完全数是6，第二个完全数是28，第三个完全数是496，后面的完全数还有8128、33550336等等。\n",
    "    求某个范围内的完全数，先获取该范围内的所有数的约数（整除数），在验证约数之和是否等于自身。\n",
    "    调用divisors(num) 获取每个数的约数\n",
    "    调用checkDivisors(divs,num) 验证约数之和是否等于自身\n",
    "    \"\"\"\n",
    "    counts = []\n",
    "    for ni in range(nums):\n",
    "        divs = divisors(ni)       \n",
    "        if divs and checkDivisors(divs[0],divs[1]):\n",
    "            print \"完美数： {}, 因子：{} \\n\".format(divs[1],divs[0])\n",
    "            counts.append((divs))\n",
    "    return counts   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 合并重叠的空间集合\n",
    "import copy\n",
    "\n",
    "class Solution:\n",
    "    def merge(self, intervals):\n",
    "        if intervals == []:\n",
    "            return intervals\n",
    "        intervals.sort()\n",
    "        begin = intervals[0][0]\n",
    "        end = intervals[0][1]\n",
    "        rst = list()\n",
    "        for i in range(1, len(intervals)):\n",
    "            if intervals[i][0] > end:\n",
    "                rst.append([begin, end])\n",
    "                begin = intervals[i][0]\n",
    "                end = intervals[i][1]\n",
    "            else:\n",
    "                if intervals[i][1] > end:\n",
    "                    end = intervals[i][1]\n",
    "        rst.append([begin, end])\n",
    "        return rst\n",
    "                    \n",
    "                    \n",
    "    def cover_spcace(self,dirA,dirB):\n",
    "        print(dirA, dirB)\n",
    "        if max(dirA[0], dirB[0]) <= min(dirA[1],dirB[1]):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "        \n",
    "    def merge_set(self, dirA,dirB):\n",
    "        newDir = (min(dirA[0],dirB[0]),max(dirA[1],dirB[1]))\n",
    "        return newDir\n",
    "        \n",
    "if __name__ == \"__main__\":\n",
    "    listA = [[1,3],[2,6],[8,10],[15,18]]\n",
    "    listA =[[1,4],[4,5]]\n",
    "    listA = [[1,4],[0,2],[3,5]]\n",
    "\n",
    "    rst = [[1,6],[8,10],[15,18]]\n",
    "    S = Solution()\n",
    "    print(S.merge(listA))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" 实现列表中重复元素最后一次出现的索引位置\n",
    "\n",
    ">>> get_last_exist_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 5)\n",
    "5\n",
    ">>> get_last_exist_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 8)\n",
    "12\n",
    ">>> get_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 5)\n",
    "5\n",
    ">>> get_dir([3,4,5,6,6,5,4,3,2,1,7,8,8,3], 8)\n",
    "12\n",
    " \"\"\"\n",
    "\n",
    "listA = [3,4,5,6,6,5,4,3,2,1,7,8,8,3]\n",
    "target = 5\n",
    "def get_last_exist_dir(listA, target):\n",
    "    # 倒置 list，查找其第一次出现的位置\n",
    "    return len(listA)- 1 - listA[::-1].index(target) \n",
    "    # for index, num in listA[::-1]:\n",
    "    #     if num == target:\n",
    "    #         return index\n",
    "\n",
    "def get_dir(listA, target):\n",
    "    # 二分法 和 快速排序想法尝试，并不能有效解决所有情况！\n",
    "    rst = None\n",
    "    length = len(listA)\n",
    "    left = 0\n",
    "    right = length - 1\n",
    "    # listA = listA[::-1]\n",
    "    while left < right:\n",
    "        mid = left + (right-left) // 2\n",
    "        # if target in listA[mid:]:\n",
    "        if target >= listA[mid]:\n",
    "            rst = mid\n",
    "            left = mid + 1\n",
    "        else:\n",
    "            right = mid - 1\n",
    "    return rst\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    import doctest\n",
    "    doctest.testmod()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 9*9乘法表\n",
    "\n",
    "#! /usr/bin/env python\n",
    "# -*- coding: utf-8 -*-\n",
    "\n",
    "\n",
    "def chengfabiao(n):\n",
    "    \"\"\" 9 * 9 乘法表\n",
    "        用逗号分隔每个打印项，如果print的最后没有逗号，每一次循环都会换行。 \n",
    "    \"\"\"\n",
    "    if n <= 0:\n",
    "        return 0\n",
    "    for cs in range(1,n):\n",
    "        print '\\n'\n",
    "        for cbs in range(1,cs + 1):\n",
    "            print \"%d x %d=%2d \"%(cs,cbs,cs * cbs) , "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\" 递增三元组子序列\n",
    "题目描述\n",
    "\n",
    "给出一个无序的整数序列，返回是否存在递增的三元组子序列。\n",
    "\n",
    "如果存在 i, j, k 使得 arr[i]<arr[j]<arr[k] and 0<i<j<k<n-1，即返回true；如果不存在则返回false。\n",
    "请给出一个O(N)时间复杂度以及O(1)额外空间的算法。\n",
    "Example 1： [1, 2, 3, 4, 5]\n",
    "返回true。\n",
    "Example 2: [5, 4, 3, 2, 1]\n",
    "返回false。\n",
    "\n",
    "\n",
    "分析解答\n",
    "\n",
    "读者不难想到穷举的方法，先穷举第一个数，再穷举找到第二个数（比第一个大），再穷举第三个数（比第二个数大），得到答案。但这样穷举过于低效，与要求的O(N)相距甚远。还有一种穷举方法是先预处理得到一个数组p，p[i]表示是否存在这样的j, j>i and arr[j]>arr[i]。这种方法符合时间复杂度的要求，但是额外空间是O(N)。因此我们需要换种思路，一边穷举一边记录已知的有用信息。当我们穷举到第i个数时，假设我们尚未找到答案，那么有以下几种情况：\n",
    "\n",
    "    我们只找到一个数（前i-1个数没有递增的两个数），此时我们记录前i-1个数的最小值。我们已找到递增的二元组子序列，此时我们需要记录的是这样的最小二元组（以第二个数为第一关键字）\n",
    "\n",
    "细心的读者可以发现，有时我们需要记录第三个数。比如已有递增子序列（3，5），之后又出现一个数1，我们必须记录1，因为如果之后出现2，（1，2）当递增序列会覆盖（3，5）。 \n",
    "\n",
    "# Testcases:\n",
    "\n",
    ">>> incressingThriplet_O1([1,2,3,4,5,6])\n",
    "True\n",
    ">>> incressingThriplet_O1([6,5,5,6,6,6])\n",
    "False\n",
    ">>> incressingThriplet_O1([8,9,3,5,8])\n",
    "True\n",
    ">>> incressingThriplet_O1([1,2,1,1,1,1])\n",
    "False\n",
    "\"\"\"\n",
    "\n",
    "# O(n)时间复杂度 O(1)空间复杂度\n",
    "def incressingThriplet_O1(numList):\n",
    "    if len(numList) <= 2: return False;\n",
    "    # 记录中间值，固定的空间(first, second)\n",
    "    # first, second 默认取 list 中最大元素，如果是最小的或随机的，第二个递增元素就不能够确定 \n",
    "    first, second = max(numList), max(numList)\n",
    "    for iNum in numList:\n",
    "        if iNum <= first:\n",
    "            first = iNum\n",
    "        if iNum > first and iNum <= second: \n",
    "            second = iNum\n",
    "        if iNum > second:\n",
    "            # print(first, second, iNum)\n",
    "            return True\n",
    "    return False\n",
    "\n",
    "if __name__ == \"__main__\":\n",
    "    import doctest\n",
    "    doctest.testmod()"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.8"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
